
//56. 合并区间
import java.util.*;
class Solution {
    public int[][] merge(int[][] intervals) {
        //利用lambda表达式，对intervals数组的数组下标0进行排序
        Arrays.sort(intervals,(a,b) -> Integer.compare(a[0],b[0]));
        //int[]是引用类型
        List<int[]> res=new ArrayList<>();

        //定义一个合并区间
        int[] cur=intervals[0];
        for(int i=1;i<intervals.length;i++){
            if(intervals[i][0]<=cur[1]){
                //左边已经是最小，无需改变，改变右边即可
                cur[1]=Math.max(cur[1],intervals[i][1]);
            }else{
                //到此说明，合并区间到头了，重新定义合并区间为intervals[i]
                res.add(cur);
                cur=intervals[i];
            }
        }
        //注意添加最后的数组
        res.add(cur);
        //toArray() 方法会使用 new int[res.size()][] 作为目标数组，并将 res 中的元素复制到该数组中。
        return res.toArray(new int[res.size()][]);
    }

}




//525. 连续数组
class Solution1 {
    public int findMaxLength(int[] nums) {
        //前缀和解题
        //思路:记录第一次出现的one-zero及其下标,第n次出现的one-zero减去第一次的下标即为相同0和1的子数组长度
        int max=0;
        HashMap<Integer,Integer> map=new HashMap<>();
        int one=0;
        int zero=0;
        map.put(0,-1);
        for(int i=0;i<nums.length;i++){
            if(nums[i]==1){
                one++;
            }else{
                zero++;
            }

            if(!map.containsKey(one-zero)){
                map.put(one-zero,i);
            }
            else{
                max=Math.max(max,i-map.get(one-zero));
            }
        }
        return max;
    }
}



//面试题 01.01. 判定字符是否唯一
class Solution2 {
    public boolean isUnique(String astr) {
        int[] arr=new int[58];
        for(int i=0;i<astr.length();i++){
            arr[astr.charAt(i)-'A']++;
            if(arr[astr.charAt(i)-'A']==2){
                return false;
            }
        }
        return true;
    }
}